package com.mymocker.algorithm;

import java.util.Arrays;

/**
 * @author zhouyang
 * @Date 2018-03-06 16:18
 * @Description 二分查找
 * @Version 1.0
 */
public class BinarySearch {


    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5, 6};
        System.out.println("循环二分查找到的索引:" + binarySearch(data, 5));
        System.out.println("递归二分查找到的索引:" + binarySearch(data, 5,0,data.length - 1));
    }


    /**
     * 循环实现二分查找
     * @param data
     * @param findValue
     * @return
     */
    private static int binarySearch(int[] data,int findValue){
        int low = 0;
        int high = data.length - 1;
        while (low <= high){
            //>>>不管正负标识位为0还是1,将该数的二进制整体右移左边用0补齐。
            int middle = (low + high) >>> 1;
            int middleVal = data[middle];
            if(middleVal > findValue){
                low  = middle - 1;
            }else if(middleVal < findValue){
                low  = middle + 1;
            }else{
                return middle;
            }
        }
        return -1;
    }

    private static int binarySearch(int[] data,int findValue,int beginIndex,int entIndex){
        //取中位数
        if(beginIndex <= entIndex && beginIndex >= 0){
            int middle = (beginIndex  + entIndex) >>> 1;
            int middleVal = data[middle];
            if(middleVal > findValue){
                return binarySearch(data,findValue,middleVal --,entIndex);
            }else  if(middleVal < findValue){
                return binarySearch(data,findValue,middleVal ++,entIndex);
            }else{
                return middle;
            }
        }
        return -1;
    }


}
